<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            示例 1:

            输入: amount = 5, coins = [1, 2, 5]
            输出: 4
            解释: 有四种方式可以凑成总金额:

            5=5
            5=2+2+1
            5=2+1+1+1
            5=1+1+1+1+1
            示例 2:

            输入: amount = 3, coins = [2]
            输出: 0
            解释: 只用面额2的硬币不能凑成总金额3。
            示例 3:

            输入: amount = 10, coins = [10]
            输出: 1
            注意，你可以假设：

            0 <= amount (总金额) <= 5000
            1 <= coin (硬币面额) <= 5000
            硬币种类不超过 500 种
            结果符合 32 位符号整数

        */


        /*
            动态规划解法
        */
        var change = function(amount, coins) {
            let dp = new Array(amount + 1).fill(0)
            dp[0] = 1
            for (let i = 0; i < coins.length; i++) {
                for (let j = coins[i]; j <= amount; j++) {
                    // j必须从coins[i]开始，j不能倒序
                    // coint[i] = 5; dp[5] = dp[5] + dp[j - coins[i]] = dp[5] + dp[5 - 5] = 3 + 1 = 4
                    // 只会影响背包容量为5的情况
                    dp[j] = dp[j] + dp[j - coins[i]]
                }
            }
            return dp[amount]
        };
        console.log(change(5, [1, 2, 5]));
    </script>
</body>

</html>